package inter;

import fn.Add;
import fn.Constant;
import fn.Function;
import fn.Multiply;
import fn.Subtract;
import fn.Variable;

public class NewtonDividedDifference extends Interpolation {

	public Function solve(double[][] array) {
		int increase = 0;
		int n = array.length;
		double[] answer = new double[n];
		double[] y = new double[n];
		for (int i = 0; i < n; i++)
			y[i] = array[i][1];

		// get double array
		for (int i = 0; i < n; i++) {

			increase++;
			answer[i] = y[0];
			if (y.length > 0) {
				double[] z = new double[y.length - 1];
				for (int j = 0; j < z.length; j++) {
					z[j] = (y[j] - y[j + 1]) / (array[j][0] - array[j + increase][0]);
				}
				y = z;
			}
		}
		return makeFunction(array, answer);
	}

	private Function makeFunction(double[][] array, double[] answer) {

		Function add = Constant.create(answer[0]);
		for (int i = 1; i < answer.length; i++) {
			Function multiply = Constant.create(answer[i]);
			for (int j = 0; j < i; j++) {
				multiply = Multiply.create(multiply, Subtract.create(Variable.create(), Constant.create(array[j][0])));
			}

			add = Add.create(add, multiply);
		}

		return add;
	}

	@Override
	public String toString() {
		return "Newton Divided Difference";
	}

}
